def floyd_warshall(W):
    D = copy.copy(W)
    for k in xrange(1, n + 1):
        for i in xrange(1, n + 1):
            for j in xrange(1, n + 1):
                D[i,j] = min(D[i, j], D[i, k] + D[k, j])
    return D

def prt_L(L):
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            print '%2d' % L[i, j],
        print

if __name__ == '__main__':
    import copy
    from collections import defaultdict
    es = [(1,2,3), (1,3,8), (1,5,-4),
          (2,4,1), (2,5,7),
          (3,2,4),
          (4,1,2), (4,3,-5),
          (5,4,6)]
    n = 5
    inf = 2**100
    W = defaultdict(lambda: inf)
    for i in xrange(1, n + 1):
        W[i, i] = 0
    for (u, v, w) in es:
        W[u, v] = w
    D = floyd_warshall(W)
    print 'D: '
    prt_L(D)
